#include <iostream>
#include <vector>

using namespace std;

// 438. 找到字符串中所有字母异位词
// https://leetcode.cn/problems/find-all-anagrams-in-a-string/description/

class Solution
{
public:
    vector<int> findAnagrams(string s, string p)
    {
        vector<int> ans;
        vector<int> recordChar(26);
        for (auto ch : p)
        {
            recordChar[ch - 'a']++;
        }

        int windowsLen = p.size();
        vector<int> curChar(26);
        int left = 0;
        int diff = 0;
        for (int i = 0; i < s.size(); i++)
        {
            char curIndex = s[i] - 'a';
            curChar[curIndex]++;
            if(curChar[curIndex] > recordChar[curIndex]){
                diff++;
            }
            if(i - left + 1 < windowsLen){
                continue;
            }
            if(diff == 0){
                ans.push_back(left);
                ans.push_back(i);
            }
            curChar[s[left] - 'a']--;
            if(curChar[s[left] - 'a'] >= recordChar[s[left] - 'a']){
                diff--;
            }
            left++;
        }
        return ans;
    }
};

int main()
{
    return 0;
}